<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>快速排序</title>

    <script>

        function quickSort(arr){

            sort(arr, 0, arr.length-1)

        }

        function sort(arr, start, end){
            

            //注意
            if(start >= end){
                return
            }

            let pivot = arr[start]
            let left = start+1;
            let right = end;

            while(true){
                

                if(left === right){

                    if(arr[left] < pivot){
                        swap(arr, start, left)
                    }

                    break;
                }


                if(arr[left]>pivot && arr[right]<pivot){
                    swap(arr, left, right) 
                }else{
                    if(arr[left]<=pivot){
                        left++;
                    }

                    if(arr[right]>=pivot){
                        right--;
                    }

                    //注意
                    if(left > right){
                        right = left;
                    }
                }

            }

            
            console.log(arr.toString());
            

            sort(arr, start, left-1);
            sort(arr, left, end);


        }

        function swap(arr, i, j){
            let a = arr[i];
            arr[i] = arr[j];
            arr[j] = a;
        }

        const arr = [7, 5, 6, 9, 6, 2, 3, 6, 1, 8, 4]

        quickSort(arr)

        console.log(arr);
        
        

    </script>
</head>

<body>

</body>

</html>